package linear

import (
    "fmt"
    "reflect"
    "strings"
)

type doublyNode struct {
    data interface{}
    pre  *doublyNode
    next *doublyNode
}

type DoublyLinkList struct {
    head *doublyNode
    last *doublyNode
    len  int
}

func NewDoublyLinkList() *DoublyLinkList {
    head := &doublyNode{nil, nil, nil}
    return &DoublyLinkList{
        head: head,
        last: nil,
        len:  0,
    }
}

func (dl *DoublyLinkList) Length() int {
    return dl.len
}

func (dl *DoublyLinkList) isEmpty() bool {
    return dl.len == 0
}

func (dl *DoublyLinkList) Get(index int) *doublyNode {
    node := dl.head
    for i := 0; i < index; i++ {
        node = node.next
    }
    return node
}

func (dl *DoublyLinkList) Insert(data interface{}) {
    lastNode := dl.Get(dl.len)
    newNode := &doublyNode{
        data: data,
        pre:  lastNode,
        next: nil,
    }
    lastNode.next = newNode
    dl.last = newNode
    dl.len++
}

func (dl *DoublyLinkList) InsertI(index int, data interface{}) {
    preNode := dl.Get(index - 1)
    curNode := preNode.next
    newNode := &doublyNode{
        data: data,
        pre:  preNode,
        next: curNode,
    }
    preNode.next = newNode
    curNode.pre = newNode
    dl.len++
}

func (dl *DoublyLinkList) Remove(index int) *doublyNode {
    preNode := dl.Get(index - 1)
    curNode := preNode.next
    nextNode := curNode.next
    preNode.next = nextNode
    nextNode.pre = preNode
    dl.len--
    return curNode
}

func (dl *DoublyLinkList) Clear() {
    dl.head.next = nil
    dl.last = nil
    dl.len = 0
}

func (dl *DoublyLinkList) IndexOf(data interface{}) int {
    node := dl.head
    for i := 0; i <= dl.len; i++ {
        if reflect.DeepEqual(node.data, data) {
            return i
        }
        node = node.next
    }
    return -1
}

func (dl *DoublyLinkList) GetFirst() *doublyNode {
    return dl.head.next
}

func (dl *DoublyLinkList) GetLast() *doublyNode {
    return dl.last
}

func (dl *DoublyLinkList) Print() {
    node := dl.head
    str := "["
    for i := 0; i < dl.len; i++ {
        node = node.next
        str += fmt.Sprintf("%v ", node)
    }
    str = strings.TrimSuffix(str, " ")
    str += "]"
    fmt.Println(str)
}
